package cn.tedu.sort;

import org.junit.Test;

public class Quick3waySort extends QuickSort {
    @Override
    protected void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo)
            return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = arr[lo];
        while (i <= gt) {
            int cmp = arr[i].compareTo(v);
            if (cmp < 0)
                exch(arr, lt++, i++);
            else if (cmp > 0)
                exch(arr, i, gt--);
            else
                i++;
        } // 现在arr[lo..lt-1] < v = arr[lt..gt] < arr[gt+1..hi]成立
        sort(arr, lo, lt - 1);
        sort(arr, gt + 1, hi);
    }

    @Test
    public void test() {
        generateNumbers();
        sort(numbers);
        show();
    }
}
